﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

//环形链表的约瑟夫问题
typedef struct ListNode
{
	int val;
	struct ListNode* next;
}LN;

//编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
//下一个人继续从 1 开始报数。
//n - 1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

//创建节点
LN* buynode(int x)
{
	LN* newnode = (LN*)malloc(sizeof(LN));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
// 创建循环链表
LN* create(int n)
{
	//创建第一个节点
	LN* phead = buynode(1);
	LN* pucr = phead;
	for (int i = 2; i <= n; i++)
	{
		pucr->next = buynode(i);
		pucr = pucr->next;
	}
	pucr->next = phead;
	return pucr;
}
int ysf(int n, int m)
{
	LN* prev = create(n);
	LN* pucr = prev->next;
	int count = 1;
	while (pucr != pucr->next)
	{
		if (count == m)
		{
			prev->next = pucr->next;
			free(pucr);
			pucr = prev->next;
			count = 1;
		}
		else
		{
			prev = pucr;
			pucr = pucr->next;
			count++;
		}
	}
	return pucr->val;
}
int main()
{
	int n = 5;
	int m = 2;
	int ret = ysf(n, m);
	printf("%d\n", ret);
	return 0;
}
